package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 * 只使用数字1到9
 * 每个数字 最多使用一次
 */

public class CombinationSumIII {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            backtracking(k, n, 1);
            return res;
        }

        // 递归函数参数：需要使用 startIndex 进行去重
        private void backtracking(int k, int n, int startIndex) {
            // 终止条件
            if (check(k, n)) {
                res.add(new ArrayList<>(path));
                return;
            }

            // 单层搜索
            for (int i = startIndex; i <= 9; i++) {
                path.add(i);
                backtracking(k, n, i + 1);
                path.remove(path.size() - 1);
            }
        }

        // 回溯终止条件：一方面数组长度达到 k，另一方面数组元素之和为 n
        private boolean check(int k, int n) {
            if (path.size() != k) return false;
            for (int i : path)
                n -= i;
            return n == 0;
        }
    }
}
